class Solution:
	# @param grid, a list of lists of integers
	# @return an integer
	def minPathSum(self, grid):
		for i in xrange(1, len(grid[0])):
			grid[0][i] += grid[0][i-1]
		for j in xrange(1, len(grid)):
			grid[j][0] += grid[j-1][0]
		for i in xrange(1, len(grid)):
			for j in xrange(1, len(grid[0])):
				grid[i][j] += min(grid[i-1][j], grid[i][j-1])
		return grid[-1][-1]

		